package solution;

/**
 * Topological.java
 * @param <V>
 * ------------------------------------------------------------------------
 * ALGORITHM 4.5 Topological sort
 *
 * Reverse postorder in a DAG is a topological sort.
 *
 * With DFS, we can topologically sort a DAG in time proportional to $V + E$.
 */
public class Topological<V> {
    private Iterable<V> order;  // topological order

    public Topological(Graph<V> graph) {
        DirectedCycle<V> cyclefinder = new DirectedCycle<>(graph);
        if (!cyclefinder.hasCycle()) {
            DepthFirstOrder<V> dfsOrder = new DepthFirstOrder<>(graph);
            order = dfsOrder.reversePost();
        }
    }

    public Iterable<V> order() {
        return order;
    }

    public boolean isDAG(){
        return order != null;
    }
}
